package com.hot100.easy;

import java.util.Stack;

/**
 * @ClassName Demo13
 * @Description  相交链表
 * @Author zt
 * @Date 15:00 2022/6/11
 * @Version 1.0
 **/
public class Demo13 {

    public static void main(String[] args) {

    }

    public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }


    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        Stack<ListNode> stackA=new Stack<>();
        Stack<ListNode> stackB=new Stack<>();

        if(headA==null||headB==null){
            return null;
        }

        while (headA!=null){
            stackA.push(headA);
            headA=headA.next;
        }
        while (headB!=null){
            stackB.push(headB);
            headB=headB.next;
        }
        ListNode tailA = stackA.pop();
        ListNode tailB = stackB.pop();
        ListNode temp=tailA;
        if(tailA!=tailB){
            return null;
        }else if(stackA.empty()||stackB.empty()){
            return temp;
        }else {
            while (!stackA.empty()&&!stackB.empty()){
                ListNode taila = stackA.pop();
                ListNode tailb = stackB.pop();
                if(taila!=tailb){
                    return temp;
                }else {
                    temp=taila;
                }
            }
        }
          return temp;
    }
}